package year2019.month08;

import java.util.LinkedList;

/**
 * LinkedList简单实现
 * @param <T>
 */
public class MyLinkedList<T> {
    private static class Node<T>{
        T item;
        Node<T> pre;
        Node<T> next;
        Node(Node<T> pre, T item, Node<T> next){
            this.item=item;
            this.pre=pre;
            this.next=next;
        }
    }

    private Node<T> first;
    private Node<T> last;
    private int size=0;

    private void linkFirst(T element){
        Node<T> f = first;
        Node<T> newNode = new Node<T>(null,element,f);
        first=newNode;
        if (f==null){   //如果f为空，说明是第一个节点
            last=newNode;
        }else{  //让原来最后节点的next指向新节点
            f.pre=newNode;
        }
        size++;
    }

    private void linkLast(T element){
        Node<T> l = last;
        Node<T> newNode = new Node<T>(l,element,null);
        last=newNode;
        if (l==null){   //如果l为空，说明是第一个节点
            first=newNode;
        }else{  //让原来最后节点的next指向新节点
            l.next=newNode;
        }
        size++;
    }

    public boolean add(T element){
        linkLast(element);
        return true;
    }

    public T get(int index){
        if (index<0 || index>=size){
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        return node(index).item;
    }

    public Node<T> node(int index){
        if (index<(size>>1)){
            Node<T> x = first;
            for (int i=0; i<index;i++){
                x = x.next;
            }
            return x;
        } else {
            Node<T> x = last;
            for (int i=size-1; i>index;i--){
                x = x.pre;
            }
            return x;
        }
    }

    public int size(){
        return size;
    }


    public static void main(String[] args){
        MyLinkedList<String> myLinkedList = new MyLinkedList<>();
        for (int i=1; i<=100; i++){
            myLinkedList.add("元素："+i);
        }
        System.out.println(myLinkedList.size());
        for (int i=0; i<myLinkedList.size(); i++){
            System.out.println(myLinkedList.get(i));
        }
//        System.out.println(myLinkedList.get(myLinkedList.size()));
    }


}
